﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DiscreteMath
{
    public class ContextFreeGrammar : ILanguageGenerator, ILanguageOperator<ContextFreeGrammar>
    {
        private char[] nonterminalsAsArray;
        private static int counter = 0;
        public static readonly int MaxDerivationTreeHeight = 100;

        public ContextFreeGrammar(ISet<char> nonterminals, ISet<string> terminals, RuleDictionary rules, char starting)
        {
            this.Nonterminals = nonterminals;
            this.nonterminalsAsArray = nonterminals.ToArray();
            this.Terminals = terminals;
            this.Rules = new RuleDictionary(rules);
            Comparer<string> comparer = Comparer<string>.Create(
                (first, second) =>
                {
                    int nonterminalsInFirst = first.Count(IsNonterminal);
                    int nonterminalsInSecond = second.Count(IsNonterminal);
                    int result = nonterminalsInFirst.CompareTo(nonterminalsInSecond);
                    return result;
                });
            foreach (var rule in this.Rules)
            {
                rule.Value.Sort(comparer);
            }
            this.StartSymbol = starting;

            if (!this.Nonterminals.IsSupersetOf(rules.Keys))
                throw new ArgumentException("there are rules whose left side is not in nonterminals");

            if (!this.Nonterminals.Contains(this.StartSymbol))
                throw new ArgumentException("the start symbol is not a nonterminal");
        }

        public ISet<char> Nonterminals { get; private set; }

        public ISet<string> Terminals { get; private set; }

        public RuleDictionary Rules { get; private set; }

        public char StartSymbol { get; private set; }

        public string GenerateWord()
        {
            return this.GenerateWord(MaxDerivationTreeHeight);
        }

        public string GenerateWord(int maxDerivationTreeHeight)
        {
            Random rng = new Random();
            ParseTree tree = new ParseTree(StartSymbol.ToString());
            Stack<ParseTree> frontier = new Stack<ParseTree>();
            frontier.Push(tree);
            bool shouldTerminate = false;
            while (frontier.Count != 0 && !shouldTerminate)
            {
                ApplyRule(frontier, (rules) => rng.Next(rules.Count));
                double terminationChance = tree.CalculateHeight() / (double) maxDerivationTreeHeight;
                shouldTerminate = rng.NextDouble() < terminationChance;
            }
            while (frontier.Count != 0)
            {
                ApplyRule(frontier, 0);
            }

            StringBuilder builder = new StringBuilder();
            IList<ParseTree> leaves = tree.CalculateLeaves();
            for (int i = 0; i < leaves.Count; i++)
            {
                if (leaves[i].Value[0] != SpecialSigns.EmptyWord)
                    builder.Append(leaves[i].Value);
            }
            return builder.ToString();
        }

        private bool IsNonterminal(char letter)
        {
            return this.Nonterminals.Contains(letter);
        }

        private void ApplyRule(Stack<ParseTree> frontier, Func<IList<string>, int> ruleIndexSelector)
        {
            ParseTree firstNonterminalNode = frontier.Pop();
            char firstNonterminal = firstNonterminalNode.Value[0];

            var rules = this.Rules[firstNonterminal];
            int ruleIndex = ruleIndexSelector(rules);
            foreach (char letter in rules[ruleIndex])
            {
                var subtree = new ParseTree(letter);
                firstNonterminalNode.AddSuccessor(subtree);
                if (IsNonterminal(letter))
                {
                    frontier.Push(subtree);
                }
            };
        }

        private void ApplyRule(Stack<ParseTree> frontier, int ruleIndex)
        {
            ParseTree firstNonterminalNode = frontier.Pop();
            char firstNonterminal = firstNonterminalNode.Value[0];

            var rules = this.Rules[firstNonterminal];
            foreach (char letter in rules[ruleIndex])
            {
                var subtree = new ParseTree(letter);
                firstNonterminalNode.AddSuccessor(subtree);
                if (IsNonterminal(letter))
                {
                    frontier.Push(subtree);
                }
            };
        }

        #region Operations

        public ContextFreeGrammar Union(ContextFreeGrammar grammar)
        {
            char renamedStartSymbol;
            ISet<char> renamedNonterminals;
            RuleDictionary renamedRules;

            Algorithms.RenameDuplicateNonterminals(this, grammar, Algorithms.RenamingFunction, out renamedNonterminals, out renamedStartSymbol, out renamedRules);

            char starting = (char)Guid.NewGuid().GetHashCode();
            ISet<char> nonterminals = this.Nonterminals.Union(renamedNonterminals).Union(starting).ToSet();
            ISet<string> terminals = this.Terminals.Union(grammar.Terminals).ToSet();
            var ruleUnion = this.Rules.Union(renamedRules).ToDictionary(x => x.Key, x => x.Value);
            RuleDictionary rules = new RuleDictionary(ruleUnion);
            rules.Add(starting, new List<string>() { this.StartSymbol.ToString(), renamedStartSymbol.ToString() });

            var union = new ContextFreeGrammar(nonterminals, terminals, rules, starting);

            
            return union;
        }

        public ContextFreeGrammar Concatenate(ContextFreeGrammar grammar)
        {
            char renamedStartSymbol;
            ISet<char> renamedNonterminals;
            RuleDictionary renamedRules;

            Algorithms.RenameDuplicateNonterminals(this, grammar, Algorithms.RenamingFunction, out renamedNonterminals, out renamedStartSymbol, out renamedRules);

            char starting = (char)Guid.NewGuid().GetHashCode();
            ISet<char> nonterminals = this.Nonterminals.Union(renamedNonterminals).Union(starting).ToSet();
            ISet<string> terminals = this.Terminals.Union(grammar.Terminals).ToSet();
            RuleDictionary rules = new RuleDictionary(this.Rules.Union(renamedRules).ToDictionary(x => x.Key, x => x.Value));
            rules.Add(starting, new List<string>() { this.StartSymbol.ToString() + renamedStartSymbol.ToString() });

            var concatenation = new ContextFreeGrammar(nonterminals, terminals, rules, starting);

            return concatenation;
        }

        public ContextFreeGrammar KleneeStar()
        {
            char starting = (char)Guid.NewGuid().GetHashCode();
            ISet<char> nonterminals = this.Nonterminals.Union(starting).ToSet();
            ISet<string> terminals = this.Terminals.ToSet();
            RuleDictionary rules = new RuleDictionary(this.Rules);
            rules.Add(starting, new List<string>() { this.StartSymbol.ToString() + starting.ToString(), SpecialSigns.EmptyWord.ToString() });

            var kleneed = new ContextFreeGrammar(nonterminals, terminals, rules, starting);

            return kleneed;
        }

        #endregion

        public string Print()
        {
            var builder = new StringBuilder();
            builder.AppendLine("Starting: " + this.StartSymbol);

            builder.AppendLine("Nonterminals: ");
            foreach (var nonTerminal in this.Nonterminals)
            {
                builder.AppendLine(nonTerminal.ToString());
            }
            builder.AppendLine("Terminals: ");
            foreach (var terminal in this.Terminals)
            {
                builder.AppendLine(terminal);
            }
            builder.AppendLine("Rules: ");
            foreach (var rule in this.Rules)
            {
                builder.AppendFormat("{0} -> {1}\n", rule.Key, rule.Value.Print("|"));
            }
            return builder.ToString();
        }

        public void FilePrettyPrint()
        {
            string content = this.Print();
            char replacement = 'A';
            foreach (var nonterminal in this.Nonterminals)
            {
                content = content.Replace(nonterminal, replacement);
                replacement++;
            }

            File.WriteAllText("Grammar.txt", content);
        }

        protected static class Algorithms
        {
            public static void RenameDuplicateNonterminals(
                ContextFreeGrammar comparer,
                ContextFreeGrammar toBeRenamed,
                Func<char, char> renamingFunction,
                out ISet<char> renamedNonterminals,
                out char renamedStartSymbol,
                out RuleDictionary renamedRules)
            {
                if (!comparer.Nonterminals.Overlaps(toBeRenamed.Nonterminals))
                {
                    renamedNonterminals = toBeRenamed.Nonterminals;
                    renamedStartSymbol = toBeRenamed.StartSymbol;
                    renamedRules = toBeRenamed.Rules;

                    return;
                }

                IEnumerable<char> intersection = comparer.Nonterminals.Intersect(toBeRenamed.Nonterminals);
                IEnumerable<char> difference = toBeRenamed.Nonterminals.Except(intersection);
                IEnumerable<char> union = comparer.Nonterminals.Union(toBeRenamed.Nonterminals);
                Dictionary<char, char> renamingRules = intersection.ToDictionary(x => x, x => renamingFunction(x));

                // Make sure that after renaming no conflicts occur
                while (comparer.Nonterminals.Overlaps(renamingRules.Values) || toBeRenamed.Nonterminals.Overlaps(renamingRules.Values))
                {
                    intersection = union.Intersect(renamingRules.Values);
                    //difference = toBeRenamed.Nonterminals.Except(renamingRules.Keys);
                    foreach (var state in intersection)
                    {
                        renamingRules[state] = renamingFunction(state);
                    }
                }

                renamedNonterminals = renamingRules.Values.Union(difference).ToSet();
                renamedStartSymbol = renamingRules.ContainsKey(toBeRenamed.StartSymbol) ? 
                    renamingRules[toBeRenamed.StartSymbol] : toBeRenamed.StartSymbol;
                renamedRules = RenameRules(toBeRenamed, renamingRules);
            }

            private static RuleDictionary RenameRules(ContextFreeGrammar toBeRenamed, Dictionary<char, char> renamingRules)
            {
                RuleDictionary renamedRules;
                renamedRules = new RuleDictionary(toBeRenamed.Rules.ToDictionary(x => x.Key, x => new List<string>(x.Value)));
                var leftSides = renamedRules.Where(x => renamingRules.ContainsKey(x.Key)).ToArray();

                foreach (var rule in leftSides)
                {
                    renamedRules.Remove(rule.Key);
                    renamedRules.Add(renamingRules[rule.Key], rule.Value);
                }

                char[] renamingNonterminalsAsArray = renamingRules.Keys.ToArray();
                foreach (var rule in renamedRules)
                {
                    var toBeReplaced = rule.Value.Where(x => x.IndexOfAny(renamingNonterminalsAsArray) != -1).ToArray();

                    foreach (var rightSide in toBeReplaced)
                    {
                        rule.Value.Remove(rightSide);
                        string replacement = rightSide;
                        foreach (char renamedNonterminal in renamingNonterminalsAsArray)
                        {
                            replacement = replacement.Replace(renamedNonterminal, renamingRules[renamedNonterminal]);
                        }
                        rule.Value.Add(replacement);
                    }
                }
                return renamedRules;
            }

            public static char RenamingFunction(char letter)
            {
                return (char)counter++;
            }
        }
    }
}
